<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(A卷,100分)- 打印机队列（Java & JS & Python）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>有5台打印机打印文件&#xff0c;每台打印机有自己的待打印队列。</p> 
<p>因为打印的文件内容有轻重缓急之分&#xff0c;所以队列中的文件有1~10不同的代先级&#xff0c;其中<strong>数字越大优先级越高</strong>。</p> 
<p>打印机会从自己的待打印队列中选择<em><strong>优先级最高</strong></em>的文件来打印。</p> 
<p>如果存在两个优先级一样的文件&#xff0c;则选择<em><strong>最早进入队列</strong></em>的那个文件。</p> 
<p>现在请你来模拟这5台打印机的打印过程。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>每个输入包含1个测试用例&#xff0c;</p> 
<p>每个测试用例第一行给出发生事件的数量N&#xff08;0 &lt; N &lt; 1000&#xff09;。</p> 
<p>接下来有 N 行&#xff0c;分别表示发生的事件。共有如下两种事件&#xff1a;</p> 
<ol><li>“IN P NUM”&#xff0c;表示有一个拥有优先级 NUM 的文件放到了打印机 P 的待打印队列中。&#xff08;0&lt; P &lt;&#61; 5, 0 &lt; NUM &lt;&#61; 10)&#xff1b;</li><li>“OUT P”&#xff0c;表示打印机 P 进行了一次文件打印&#xff0c;同时该文件从待打印队列中取出。&#xff08;0 &lt; P &lt;&#61; 5&#xff09;。</li></ol> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<ul><li>对于每个测试用例&#xff0c;每次”OUT P”事件&#xff0c;请在一行中<strong>输出文件的编号</strong>。</li><li>如果此时没有文件可以打印&#xff0c;请输出”<strong>NULL</strong>“。</li><li>文件的编号定义为”IN P NUM”事件发生第 x 次&#xff0c;此处待打印文件的编号为x。编号从<strong>1</strong>开始。</li></ul> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">7<br /> IN 1 1<br /> IN 1 2<br /> IN 1 3<br /> IN 2 1<br /> OUT 1<br /> OUT 2<br /> OUT 2</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">3<br /> 4<br /> NULL</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">无</td></tr></tbody></table> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:85px;">输入</td><td style="width:413px;">5<br /> IN 1 1<br /> IN 1 3<br /> IN 1 1<br /> IN 1 3<br /> OUT 1</td></tr><tr><td style="width:85px;">输出</td><td style="width:413px;">2</td></tr><tr><td style="width:85px;">说明</td><td style="width:413px;">无</td></tr></tbody></table> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>本题可以基于优先队列实现打印机总是打印优先级最高的文件。</p> 
<p>优先队列&#xff0c;如果想简单一点的话&#xff0c;则可以基于有序数组实现&#xff0c;但是有序数组是整体有序&#xff0c;每次有新任务入队&#xff0c;都需要O(n)时间复杂度维持。</p> 
<p>优先队列最好是基于堆结构实现&#xff0c;所谓堆结构&#xff0c;即一颗完全二叉树。本题是优先级数值越大&#xff0c;优先级越高&#xff0c;因此我们可以使用大顶堆。</p> 
<p>关于基于堆结构实现优先队列&#xff0c;可以参考</p> 
<p><a href="https://blog.csdn.net/qfc_128220/article/details/127695013" title="LeetCode - 1705 吃苹果的最大数目_伏城之外的博客-CSDN博客">LeetCode - 1705 吃苹果的最大数目_伏城之外的博客-CSDN博客</a></p> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">JavaScript算法源码</h4> 
<p>基于有序数组实现优先队列</p> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines &#61; [];
let n;
rl.on(&#34;line&#34;, (line) &#61;&gt; {
  lines.push(line);

  if (lines.length &#61;&#61;&#61; 1) {
    n &#61; parseInt(lines[0]);
  }

  if (n &amp;&amp; lines.length &#61;&#61;&#61; n &#43; 1) {
    lines.shift();

    const tasks &#61; lines.map((line) &#61;&gt; line.split(&#34; &#34;));

    getResult(tasks);

    lines.length &#61; 0;
  }
});

function getResult(tasks) {
  const print &#61; {};

  let taskId &#61; 1;
  for (let i &#61; 0; i &lt; tasks.length; i&#43;&#43;) {
    const [type, printId, priority] &#61; tasks[i];

    if (type &#61;&#61;&#61; &#34;IN&#34;) {
      const arr &#61; [taskId, priority, i]; // i 是先来后到的顺序
      if (!print[printId]) {
        print[printId] &#61; []; // 基于数组实现优先队列
      }
      print[printId].push(arr);
      print[printId].sort((a, b) &#61;&gt; (a[1] !&#61; b[1] ? b[1] - a[1] : a[2] - b[2])); // 维持高优先级在头部&#xff0c;如果优先级相同&#xff0c;则按先来后到
      taskId&#43;&#43;;
    } else {
      if (!print[printId] || print[printId].length &#61;&#61; 0) {
        console.log(&#34;NULL&#34;);
      } else {
        const arr &#61; print[printId].shift();
        console.log(arr ? arr[0] : &#34;NULL&#34;);
      }
    }
  }
}
</code></pre> 
<p></p> 
<h4>Java算法源码</h4> 
<p>Java已经有优先队列实现类PriorityQueue&#xff0c;因此可以直接使用它。</p> 
<pre><code class="language-java">import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    int n &#61; Integer.parseInt(sc.nextLine());
    String[][] tasks &#61; new String[n][];

    for (int i &#61; 0; i &lt; n; i&#43;&#43;) {
      String[] s &#61; sc.nextLine().split(&#34; &#34;);
      tasks[i] &#61; s;
    }

    getResult(tasks);
  }

  public static void getResult(String[][] tasks) {
    // print中存放每台打印机的等待队列
    HashMap&lt;String, PriorityQueue&lt;int[]&gt;&gt; print &#61; new HashMap&lt;&gt;();

    // 文件的编号定义为”IN P NUM”事件发生第 x 次&#xff0c;此处待打印文件的编号为x。编号从1开始。
    int x &#61; 1;
    for (int i &#61; 0; i &lt; tasks.length; i&#43;&#43;) {
      String[] task &#61; tasks[i];
      // IN,OUT都有type和printId
      String type &#61; task[0];
      String printId &#61; task[1];

      if (&#34;IN&#34;.equals(type)) {
        // IN还有priority
        String priority &#61; task[2];
        // arr是打印任务
        int[] arr &#61; {x, Integer.parseInt(priority), i}; // i代表先来后到的顺序
        // 为打印机printId设置打印优先级&#xff0c;打印任务的priority越大&#xff0c;优先级越高
        print.putIfAbsent(
            printId,
            new PriorityQueue&lt;&gt;(
                (a, b) -&gt;
                    a[1] !&#61; b[1] ? b[1] - a[1] : a[2] - b[2])); // 优先按priority&#xff0c;如果priority相同&#xff0c;按先来后到i
        // 将打印任务加入对应打印机
        print.get(printId).offer(arr);
        x&#43;&#43;;
      } else {
        // 打印机等待队列中取出优先级最高的打印任务arr
        if (!print.containsKey(printId) || print.get(printId).isEmpty()) {
          // 如果此时没有文件可以打印&#xff0c;请输出”NULL“。
          System.out.println(&#34;NULL&#34;);
        } else {
          int[] arr &#61; print.get(printId).poll();
          if (arr !&#61; null) System.out.println(arr[0]); // arr[0]是x
          else System.out.println(&#34;NULL&#34;);
        }
      }
    }
  }
}
</code></pre> 
<p></p> 
<h4>Python算法源码</h4> 
<pre><code class="language-python">import queue

# 输入获取
n &#61; int(input())

tasks &#61; []
for i in range(n):
    tasks.append(input().split())


class Task:
    def __init__(self, taskId, priority, index):
        &#34;&#34;&#34;
        :param taskId: 任务ID
        :param priority: 任务优先级
        :param index: 任务到达顺序
        &#34;&#34;&#34;
        self.taskId &#61; taskId
        self.priority &#61; priority
        self.index &#61; index

    def __lt__(self, other):
        if self.priority !&#61; other.priority:
            return self.priority &gt; other.priority
        else:
            return self.index &lt; other.index


# 算法入口
def getResult(tasks):
    printer &#61; {}

    taskId &#61; 1
    for i in range(len(tasks)):
        task &#61; tasks[i]

        type &#61; task[0]
        printerId &#61; task[1]

        if type &#61;&#61; &#34;IN&#34;:
            priority &#61; task[2]
            if printer.get(printerId) is None:
                printer[printerId] &#61; queue.PriorityQueue()
            printer[printerId].put(Task(taskId, int(priority), i))
            taskId &#43;&#61; 1
        else:
            if printer.get(printerId) is None or printer[printerId].qsize() &#61;&#61; 0:
                print(&#34;NULL&#34;)
            else:
                t &#61; printer[printerId].get()
                print(t.taskId)


getResult(tasks)
</code></pre>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>